package interviewClassic150;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;

public class checkSubTree {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
        //先广搜，搜出来与t2值相等的节点，然后在内部深搜
        boolean flag = bfs(t1, t2);
        return flag;
    }

    private boolean bfs(TreeNode t1, TreeNode t2) {
        //队列用于广搜
        Deque<TreeNode> que = new ArrayDeque<>();
        //广搜
        TreeNode p = t1;
        que.addLast(p);
        while (!que.isEmpty()) {
            p = que.removeFirst();
            if (p.val == t2.val) {
                boolean flag = dfs(p, t2);
                if (flag) return true;
            }

            //左右子节点入队
            if (p.left != null) que.addLast(p.left);
            if (p.right != null) que.addLast(p.right);
        }

        return false;
    }

    private boolean dfs(TreeNode t1Sub, TreeNode t2Sub) {
        //值不相等直接返回错误
        if (t1Sub.val != t2Sub.val) return false;
        //值相等
        boolean left = true;
        if (t1Sub.left != null && t2Sub.left != null) left = dfs(t1Sub.left, t2Sub.left);
        else if ((t1Sub.left == null && t2Sub.left != null)
                || (t1Sub.left != null && t2Sub.left == null)) left = false;

        boolean right = true;
        if (t1Sub.right != null && t2Sub.right != null) right = dfs(t1Sub.right, t2Sub.right);
        else if ((t1Sub.right == null && t2Sub.right != null)
                || (t1Sub.right != null && t2Sub.right == null)) right = false;

        return left && right;
    }

    public TreeNode constructTree(Integer[] nums, int i) {
        if (i >= nums.length) return null;
        if (nums[i] == null) return null;
        TreeNode node = new TreeNode(nums[i]);
        node.left = constructTree(nums, 2 * i + 1);
        node.right = constructTree(nums, 2 * i + 2);
        return node;
    }

    @Test
    public void test() {
        Integer[] t1Nums = {1,null,2,4};
        Integer[] t2Nums = {3,2};

        TreeNode t1 = constructTree(t1Nums,0);
        TreeNode t2 = constructTree(t2Nums,0);

        boolean flag = checkSubTree(t1, t2);
        System.out.println(flag);
    }
}
